package test;
import java.util.Arrays;


public class MergeSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arr = {9, 1, 5, 0, 2, 4, 8, 6, 3, 7};
		sort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}

	public static void sort(int[] arr, int p, int r)
	{
		if(p == r) return;

		int q = (r + p) / 2;
		sort(arr, p, q);
		sort(arr, q + 1, r);
		merge1(arr, p, q, r);
	}

	private static void merge(int[] arr, int p, int q, int r)
	{
		int[] left = new int[q - p + 2];
		int[] right = new int[r - q + 1];
		
		for(int i = 0; i < left.length - 1; i ++)
		{
			left[i] = arr[p + i];
		}
		left[left.length - 1] = Integer.MAX_VALUE;

		for(int i = 0; i < right.length - 1; i ++)
		{
			right[i] = arr[q + i + 1];
		}
		right[right.length - 1] = Integer.MAX_VALUE;

		int i = 0, j = 0;
		for(int k = p; k <= r; k ++)
		{
			if(left[i] < right[j])
			{
				arr[k] = left[i];
				i ++;
			}
			else
			{
				arr[k] = right[j];
				j ++;
			}
		}
	}

	private static void merge1(int[] arr, int p, int q, int r)
	{
		int[] left = new int[q - p + 1];
		int[] right = new int[r - q];
		
		for(int i = 0; i < left.length; i ++)
		{
			left[i] = arr[p + i];
		}

		for(int i = 0; i < right.length; i ++)
		{
			right[i] = arr[q + i + 1];
		}

		int i = 0, j = 0;
		for(int k = p; k <= r; k ++)
		{
			if(i < left.length && (j >= right.length || left[i] < right[j]))
			{
				arr[k] = left[i];
				i ++;
			}
			else
			{
				arr[k] = right[j];
				j ++;
			}
		}
	}
}
